package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: xiaomi
 * @date: 2021/3/13
 * @description: 188. 买卖股票的最佳时机 IV
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
public class C_188_买卖股票的最佳时机IV {

    public static void main(String[] args) {

    }

    /**
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        //边界判断
        if (len <1||k<1){
            return 0;
        }
        int size = 2 * k + 1;
        int[][] dp = new int[len][2 * k + 1];
        for (int i = 0; i < size; i++) {
            if ((i & 1) == 0) {
                //偶数
                dp[0][i] = 0;
            } else {
                dp[0][i] = -prices[0];
            }
        }
        for (int i = 1; i < len; i++) {
            dp[i][0] = 0;
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            for (int j = 2; j < size; j++) {
                if ((j&1)==0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j-1] + prices[i]);
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j-1] - prices[i]);
                }
            }
//            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
//            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[len - 1][size - 1];
    }
}
